Search results for "Binary decision diagram"
showing 6 items of 6 documents
Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams
2017
We consider Quantum OBDD model. It is restricted version of read-once Quantum Branching Programs, with respect to “width” complexity. It is known that maximal complexity gap between deterministic and quantum model is exponential. But there are few examples of such functions. We present method (called “reordering”), which allows to build Boolean function g from Boolean Function f, such that if for f we have gap between quantum and deterministic OBDD complexity for natural order of variables, then we have almost the same gap for function g, but for any order. Using it we construct the total function REQ which deterministic OBDD complexity is \(2^{\varOmega (n/log n)}\) and present quantum OBD…
Very Narrow Quantum OBDDs and Width Hierarchies for Classical OBDDs
2014
In the paper we investigate a model for computing of Boolean functions – Ordered Binary Decision Diagrams (OBDDs), which is a restricted version of Branching Programs. We present several results on the comparative complexity for several variants of OBDD models. We present some results on the comparative complexity of classical and quantum OBDDs. We consider a partial function depending on a parameter k such that for any k > 0 this function is computed by an exact quantum OBDD of width 2, but any classical OBDD (deterministic or stable bounded-error probabilistic) needs width 2 k + 1. We consider quantum and classical nondeterminism. We show that quantum nondeterminism can be more efficient …
Team Theory and Person-by-Person Optimization with Binary Decisions
2012
In this paper, we extend the notion of person-by-person (pbp) optimization to binary decision spaces. The novelty of our approach is the adaptation to a dynamic team context of notions borrowed from the pseudo-boolean optimization field as completely local-global or unimodal functions and submodularity. We also generalize the concept of pbp optimization to the case where groups of $m$ decisions makers make joint decisions sequentially, which we refer to as $m$b$m$ optimization. The main contribution is a description of sufficient conditions, verifiable in polynomial time, under which a pbp or an $m$b$m$ optimization algorithm converges to the team-optimum. As a second contribution, we prese…
Generalized person-by-person optimization in team problems with binary decisions
2008
In this paper, we extend the notion of person by person optimization to binary decision spaces. The novelty of our approach is the adaptation to a dynamic team context of notions borrowed from the pseudo-boolean optimization field as completely local-global or unimodal functions and sub- modularity. We also generalize the concept of pbp optimization to the case where the decision makers (DMs) make decisions sequentially in groups of m, we call it mbm optimization. The main contribution are certain sufficient conditions, verifiable in polynomial time, under which a pbp or an mbm optimization algorithm leads to the team-optimum. We also show that there exists a subclass of sub-modular team pr…
Manipulating the alpha level cannot cure significance testing
2018
We argue that making accept/reject decisions on scientific hypotheses, including a recent call for changing the canonical alpha level from p = 0.05 to p = 0.005, is deleterious for the finding of new discoveries and the progress of science. Given that blanket and variable alpha levels both are problematic, it is sensible to dispense with significance testing altogether. There are alternatives that address study design and sample size much more directly than significance testing does; but none of the statistical tools should be taken as the new magic method giving clear-cut mechanical answers. Inference should not be based on single studies at all, but on cumulative evidence from multiple in…
<title>Spectral/spatial integration effects on information extraction from multispectral data: multiresolution approaches</title>
1995
New techniques for information extraction from multispectral data require physical modeling to understand the energy transfer at the atmosphere/surface interface and to develop appropriate inversion procedures, in combination with advanced processing techniques. A multi-step procedure is proposed in this work: the first step implies a binary decision about the second step to be applied in each case. If the pixel is considered as being a `pure' pixel, through a spectral/spatial classification procedure based on multiresolution techniques, then numerical inversion techniques, based on a multiple-scattering reflectance model, are used to extract parameters representing specific surface propert…